// coding: utf-8
// @Author : lryself
// @Date : 2020/11/1 0:59
// @Software: GoLand

package main

func main() {
	
}
func wordBreak(s string, wordDict []string) []string {
	ch_dict:=make(map[int32]bool)
	dict:=make(map[string]int)
	maxlen:=0
	result := []string{}
	for _,value:=range wordDict{
		if len(value)>maxlen{
			maxlen=len(value)
		}
		dict[value]=len(value)
		for _,ch :=range value{
			ch_dict[ch]=true
		}
	}
	for _,ch :=range s{
		if !ch_dict[ch]{
			return result
		}
	}
	temp:=""
	index_list:=[]int{0}
	index:=0
	for index<len(index_list){
		for i:=index_list[index];i<len(s);i++{
			temp=temp+string(s[i])
			_,ok:=dict[temp]
			if ok{
				base:=""
				if index>=len(result){
					base=""
					result=append(result,temp)
				}else {
					base=result[index]+" "
					result[index]=result[index]+" "+temp
				}
				temp1:=temp
				for j:=i+1;j-i<=maxlen-dict[temp]&&j<len(s);j++{
					temp1+=string(s[j])
					_,ok1:=dict[temp1]
					if ok1{
						index_list=append(index_list, j+1)
						result=append(result, base+temp1)
					}
				}
				temp=""
			}
		}
		if temp != ""{
			index_list[index]=-1
		}
		index++
		temp=""
	}
	true_result:=[]string{}
	for key,i := range index_list{
		if i!=-1{
			true_result=append(true_result, result[key])
		}
	}
	return true_result
}